package cn.lintcode;

/**
 * @author labvi
 * @version 1.0.0
 */
public class FibonacciII {
    static class Matrix{
        long[][] mat = new long[2][2];
        public void zero() {
            for(int i = 0; i < 2; ++i){
                for(int j = 0; j < 2; ++j){
                    mat[i][j] = 0;
                }
            }
        }
        public void unit() {
            for(int i = 0; i < 2; ++i){
                for(int j = 0; j < 2; ++j){
                    mat[i][j] = (i == j ? 1 : 0);
                }
            }
        }
        public Matrix mul(Matrix m){
            Matrix tmp = new Matrix();
            tmp.zero();
            for(int i = 0 ; i < 2; ++i){
                for(int k = 0 ; k < 2; ++k){
                    if(mat[i][k]==0) {continue;}
                    for(int j = 0 ; j < 2; ++j){
                        tmp.mat[i][j] += mat[i][k] * m.mat[k][j];
                        tmp.mat[i][j] %= 10000;
                    }
                }
            }
            return tmp;
        }
    }
    public static class Solution {
        /**
         * @param A: an integer
         * @return: return a string
         */
        public Matrix power(Matrix A, int a) {
            Matrix B = new Matrix();
            B.unit();
            while(a > 0) {
                if(a % 2 == 1) {
                    B = B.mul(A);
                }
                A = A.mul(A);
                a /= 2;
            }
            return B;
        }
        public String lastFourDigitsOfFn(int n) {
            // write your code here
            if(n == 0) {return "0";}
            Matrix A = new Matrix();
            A.mat[0][0] = 1; A.mat[0][1] = 1;
            A.mat[1][0] = 1; A.mat[1][1] = 0;
            Matrix m = power(A, n - 1);
            long p = m.mat[0][0];
            String ans = "";
            if(p > 0) {
                for(int i = 0; i < 4; ++i) {
                    ans = (char)('0' + p % 10) + ans;
                    p /= 10;
                }
            }else { ans = "0";}
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lastFourDigitsOfFn(1000000));
    }
}
